home *** CD-ROM | disk | FTP | other *** search
/ CD Classic / CD CLASSIC #1.iso / chess / search.c < prev    next >
C/C++ Source or Header  |  1991-08-15  |  45KB  |  1,670 lines
  1. /*
  2.   C source for GNU CHESS
  3.  
  4.   Revision: 1990-12-26
  5.  
  6.   Modified by Daryl Baker for use in MS WINDOWS environment
  7.  
  8.   Copyright (C) 1986, 1987, 1988, 1989, 1990 Free Software Foundation, Inc.
  9.   Copyright (c) 1988, 1989, 1990  John Stanback
  10.  
  11.   This file is part of CHESS.
  12.  
  13.   CHESS is distributed in the hope that it will be useful, but WITHOUT ANY
  14.   WARRANTY.  No author or distributor accepts responsibility to anyone for
  15.   the consequences of using it or for whether it serves any particular
  16.   purpose or works at all, unless he says so in writing.  Refer to the CHESS
  17.   General Public License for full details.
  18.  
  19.   Everyone is granted permission to copy, modify and redistribute CHESS, but
  20.   only under the conditions described in the CHESS General Public License.
  21.   A copy of this license is supposed to have been given to you along with
  22.   CHESS so you can know your rights and responsibilities.  It should be in a
  23.   file named COPYING.  Among other things, the copyright notice and this
  24.   notice must be preserved on all copies.
  25. */
  26.  
  27. #define NOATOM 
  28. #define NOCLIPBOARD
  29. #define NOCREATESTRUCT
  30. #define NOFONT
  31. #define NOREGION
  32. #define NOSOUND
  33. #define NOWH
  34. #define NOWINOFFSETS
  35. #define NOCOMM
  36. #define NOKANJI
  37.  
  38. #include <windows.h>
  39. #include <string.h>
  40. #include <time.h>
  41. #include <stdlib.h>
  42. #include <malloc.h>
  43. #include <stdio.h>
  44.  
  45. #include "gnuchess.h"
  46. #include "defs.h"
  47.  
  48. #if ttblsz
  49. extern unsigned long hashkey, hashbd;
  50. /*extern struct hashval hashcode[2][7][64];*/
  51. /*extern struct hashentry huge ttable[2][ttblsz];*/
  52. extern struct hashval far *hashcode;
  53. extern struct hashentry far *ttable;
  54. #endif /* ttblsz */
  55.  
  56. /*extern unsigned char history[8192];*/
  57. extern unsigned char far * history;
  58.  
  59. extern short rpthash[2][256];
  60. /*extern unsigned char nextpos[8][64][64];*/
  61. /*extern unsigned char nextdir[8][64][64];*/
  62. extern unsigned char far *nextpos;
  63. extern unsigned char far *nextdir;
  64.  
  65. extern short FROMsquare, TOsquare, Zscore, zwndw;
  66. extern unsigned short PV, Swag0, Swag1, Swag2, Swag3, Swag4;
  67. extern unsigned short killr0[maxdepth], killr1[maxdepth];
  68. extern unsigned short killr2[maxdepth], killr3[maxdepth];
  69. extern short Pscore[maxdepth], Tscore[maxdepth];
  70. extern unsigned long hashkey, hashbd;
  71. extern short ChkFlag[maxdepth], CptrFlag[maxdepth], PawnThreat[maxdepth];
  72. extern short mtl[2], pmtl[2], emtl[2], hung[2];
  73. extern short player, xwndw, rehash;
  74. extern short PieceCnt[2];
  75. extern long NodeCnt, ETnodes, EvalNodes, HashCnt, FHashCnt, HashCol;
  76. extern short HasKnight[2], HasBishop[2], HasRook[2], HasQueen[2];
  77. extern short Pindex[64];
  78.  
  79. static short _based(_segname("_CODE")) rank7[3] = {6, 1, 0};
  80. static short _based(_segname("_CODE")) kingP[3] = {4, 60, 0};
  81. static short _based(_segname("_CODE")) value[7] =
  82. {0, valueP, valueN, valueB, valueR, valueQ, valueK};
  83.  
  84. static short _based(_segname("_CODE")) sweep[8] =
  85. {false, false, false, true, true, true, false, false};
  86.  
  87. static short _based(_segname("_CODE")) ptype[2][8] = {
  88.   no_piece, pawn, knight, bishop, rook, queen, king, no_piece,
  89.   no_piece, bpawn, knight, bishop, rook, queen, king, no_piece};
  90.  
  91. static short _based(_segname("_CODE")) control[7] =
  92. {0, ctlP, ctlN, ctlB, ctlR, ctlQ, ctlK};
  93.  
  94. /* ............    MOVE GENERATION & SEARCH ROUTINES    .............. */
  95.  
  96. void
  97. pick (short int p1, short int p2)
  98.  
  99. /*
  100.   Find the best move in the tree between indexes p1 and p2. Swap the best
  101.   move into the p1 element.
  102. */
  103.  
  104. {
  105.   register short p, s;
  106.   short p0, s0;
  107.   struct leaf temp;
  108.  
  109.   s0 = Tree[p1].score;
  110.   p0 = p1;
  111.   for (p = p1 + 1; p <= p2; p++)
  112.     if ((s = Tree[p].score) > s0)
  113.       {
  114.         s0 = s;
  115.         p0 = p;
  116.       }
  117.   if (p0 != p1)
  118.     {
  119.       temp = Tree[p1];
  120.       Tree[p1] = Tree[p0];
  121.       Tree[p0] = temp;
  122.     }
  123. }
  124.  
  125. void
  126. SelectMove (HWND hWnd, short int side, short int iop)
  127.  
  128. /*
  129.   Select a move by calling function search() at progressively deeper ply
  130.   until time is up or a mate or draw is reached. An alpha-beta window of -90
  131.   to +90 points is set around the score returned from the previous
  132.   iteration. If Sdepth != 0 then the program has correctly predicted the
  133.   opponents move and the search will start at a depth of Sdepth+1 rather
  134.   than a depth of 1.
  135. */
  136.  
  137. {
  138.   static short i, tempb, tempc, tempsf, tempst, xside, rpt;
  139.   static short alpha, beta, score;
  140.  
  141.   flag.timeout = false;
  142.   xside = otherside[side];
  143.   if (iop != 2)
  144.     player = side;
  145.   if (TCflag)
  146.     {
  147.       if ((TimeControl.moves[side] + 3) != 0)
  148.         ResponseTime = (TimeControl.clock[side]) /
  149.           (TimeControl.moves[side] + 3) -
  150.           OperatorTime;
  151.       else
  152.         ResponseTime = 0;
  153.       ResponseTime += (ResponseTime * TimeControl.moves[side]) / (2 * TCmoves + 1);
  154.     }
  155.   else
  156.     ResponseTime = Level;
  157.   if (iop == 2)
  158.     ResponseTime = 99999;
  159.   if (Sdepth > 0 && root->score > Zscore - zwndw)
  160.     ResponseTime -= ft;
  161.   else if (ResponseTime < 1)
  162.     ResponseTime = 1;
  163.   ExtraTime = 0;
  164.   ExaminePosition ();
  165.   ScorePosition (side, &score);
  166.   /* Pscore[0] = -score; */
  167.   ShowSidetoMove ();
  168.  
  169.   if (Sdepth == 0)
  170.     {
  171. #if ttblsz
  172.       /* ZeroTTable (); */
  173. #endif /* ttblsz */
  174.       SearchStartStuff (side);
  175. #ifdef NOMEMSET
  176.       for (i = 0; i < 8192; i++)
  177. /*        history[i] = 0; */
  178.           *(history+i) = 0;
  179.  
  180. #else
  181.       _fmemset ( history, 0, 8192 * sizeof (char));
  182. #endif /* NOMEMSET */
  183.       FROMsquare = TOsquare = -1;
  184.       PV = 0;
  185.       if (iop != 2)
  186.         hint = 0;
  187.       for (i = 0; i < maxdepth; i++)
  188.         PrVar[i] = killr0[i] = killr1[i] = killr2[i] = killr3[i] = 0;
  189.       alpha = score - 90;
  190.       beta = score + 90;
  191.       rpt = 0;
  192.       TrPnt[1] = 0;
  193.       root = &Tree[0];
  194.       MoveList (side, 1);
  195.       for (i = TrPnt[1]; i < TrPnt[2]; i++)
  196.         pick (i, TrPnt[2] - 1);
  197.       if (Book != NULL)
  198.         OpeningBook (&hint);
  199.       if (Book != NULL)
  200.         flag.timeout = true;
  201.       NodeCnt = ETnodes = EvalNodes = HashCnt = FHashCnt = HashCol = 0;
  202.       Zscore = 0;
  203.       zwndw = 20;
  204.     }
  205.   while (!flag.timeout && Sdepth < MaxSearchDepth)
  206.     {
  207.       Sdepth++;
  208.       ShowDepth (' ');
  209.       score = search (hWnd, side, 1, Sdepth, alpha, beta, PrVar, &rpt);
  210.       for (i = 1; i <= Sdepth; i++)
  211.         killr0[i] = PrVar[i];
  212.       if (score < alpha)
  213.         {
  214.           ShowDepth ('\xbb' /*'-'*/);
  215.           ExtraTime = 10 * ResponseTime;
  216.           /* ZeroTTable (); */
  217.           score = search (hWnd, side, 1, Sdepth, -9000, score, PrVar, &rpt);
  218.         }
  219.       if (score > beta && !(root->flags & exact))
  220.         {
  221.           ShowDepth ('\xab' /*'+'*/);
  222.           ExtraTime = 0;
  223.           /* ZeroTTable (); */
  224.           score = search (hWnd, side, 1, Sdepth, score, 9000, PrVar, &rpt);
  225.         }
  226.       score = root->score;
  227.       if (!flag.timeout)
  228.         for (i = TrPnt[1] + 1; i < TrPnt[2]; i++)
  229.           pick (i, TrPnt[2] - 1);
  230.       ShowResults (score, PrVar, '\xb7' /*'.'*/);
  231.       for (i = 1; i <= Sdepth; i++)
  232.         killr0[i] = PrVar[i];
  233.       if (score > Zscore - zwndw && score > Tree[1].score + 250)
  234.         ExtraTime = 0;
  235.       else if (score > Zscore - 3 * zwndw)
  236.         ExtraTime = ResponseTime;
  237.       else
  238.         ExtraTime = 3 * ResponseTime;
  239.       if (root->flags & exact)
  240.         flag.timeout = true;
  241.       if (Tree[1].score < -9000)
  242.         flag.timeout = true;
  243.       if (4 * et > 2 * ResponseTime + ExtraTime)
  244.         flag.timeout = true;
  245.       if (!flag.timeout)
  246.         {
  247.           Tscore[0] = score;
  248.           if (Zscore == 0)
  249.             Zscore = score;
  250.           else
  251.             Zscore = (Zscore + score) / 2;
  252.         }
  253.       zwndw = 20 + abs (Zscore / 12);
  254.       beta = score + Bwindow;
  255.       if (Zscore < score)
  256.         alpha = Zscore - Awindow - zwndw;
  257.       else
  258.         alpha = score - Awindow - zwndw;
  259.     }
  260.  
  261.   score = root->score;
  262.   if (rpt >= 2 || score < -12000)
  263.     root->flags |= draw;
  264.   if (iop == 2)
  265.     return;
  266.   if (Book == NULL)
  267.     hint = PrVar[2];
  268.   ElapsedTime (1);
  269.  
  270.   if (score > -9999 && rpt <= 2)
  271.     {
  272.       MakeMove (side, root, &tempb, &tempc, &tempsf, &tempst, &INCscore);
  273.